#pragma once
#include <iostream>
#include <cstdio>
#include <cassert>
#include <unistd.h>

namespace ns_list
{
    template <class T>
    struct ListNode
    {
        T _val;
        ListNode<T>* _prev;
        ListNode<T>* _next;

        ListNode(const T& val = T()) : _val(val), _prev(nullptr), _next(nullptr)
        {}
    };

    template <class T>
    class list;

    template<class T>
    class Iterator
    {
    public:
        typedef ListNode<T> Node;
        Iterator(Node* lt) : node(lt)
        {}

        Iterator& operator++()
        {
            node = node->_next;
            return *this;
        }

        Iterator& operator--()
        {
            node = node->_prev;
            return *this;
        }

        T& operator*() const
        {
            return node->_val;
        }

        T* operator->() const
        {
            return &node->_val;
        }

        bool operator!=(const Iterator& lt) const
        {
            return lt.node != node;
        }

        bool operator==(const Iterator& lt) const
        {
            return lt.node == node;
        }
    public:
        Node* node;
    };

    template <class T>
    class list
    {
    public:
        typedef ListNode<T> Node;

        typedef Iterator<T> iterator;
        typedef const Iterator<T> const_iterator;

        iterator begin()
        {
            return iterator(_node->_next);
        }

        iterator end()
        {
            return iterator(_node);
        }

        const_iterator begin() const
        {
            return const_iterator(_node->_next);
        }

        const_iterator end() const
        {
            return const_iterator(_node);
        }

        list<T>(const T& val = T())
        {
            _node = new Node(val);
            _node->_prev = _node;
            _node->_next = _node;
        }

        template <class InputIterator>
        list<T>(InputIterator first, InputIterator last)
        {
            _node = new Node(T());
            _node->_prev = _node;
            _node->_next = _node;
            while(first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        list<T>(const list<T>& l)
        {
            _node = new Node(T());
            _node->_prev = _node;
            _node->_next = _node;
            list<T> tmp(l.begin(), l.end());
            std::swap(_node, tmp._node);
        }

        list<T>& operator=(list<T> l)
        {
            std::swap(_node, l._node);

            return *this;
        }

        void push_back(const T& val)
        {
            Node* newnode = new Node(val);
            _node->_prev->_next = newnode;
            newnode->_prev = _node->_prev;
            newnode->_next = _node;
            _node->_prev = newnode;
        }

        void push_front(const T& val)
        {
            Node* newnode = new Node(val);
            newnode->_prev = _node;
            newnode->_next = _node->_next;
            _node->_next->_prev = newnode;
            _node->_next = newnode;
        }

        iterator insert(iterator pos, const T& val)
        {
            Node* pre = pos.node->_prev;
            Node* newnode = new Node(val);
            newnode->_prev = pre;
            pre->_next = newnode;
            newnode->_next = pos.node;
            pos.node->_prev = newnode;

            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            assert(pos.node != _node);
            Node* pre = pos.node->_prev;
            Node* nxt = pos.node->_next;
            pre->_next = nxt;
            nxt->_prev = pre;
            delete pos.node;
            pos.node = nullptr;

            return iterator(nxt);
        }

        void pop_back()
        {
            assert(_node != _node->_next);
            Node* tail = _node->_prev;
            _node->_prev = tail->_prev;
            tail->_prev->_next = _node;
            delete tail;
            tail = nullptr;
        }

        void pop_front()
        {
            assert(_node != _node->_next);
            Node* head = _node->_next;
            _node->_next = head->_next;
            head->_next->_prev = _node;
            delete head;
            head = nullptr;
        }

        void Show()
        {
            Node* cur = _node->_next;
            while(cur != _node)
            {
                std::cout << cur->_val << " ";
                cur = cur->_next;
            }
            std::cout << std::endl;
        }

        bool empty()
        {
            return _node == _node->_next;
        }

        ~list()
        {
            Node* cur = _node->_next;
            while(cur != _node)
            {
                Node* Next = cur->_next;
                std::cout << "cur : " << cur->_val << std::endl;
                delete cur;
                cur = Next;
            }
            delete _node;
            _node = nullptr;
        }
    private:
        Node* _node;
    };
}